#include <stdio.h>
#include <stdlib.h>

#include "Merge.h"


void MergeList_1(SqList L1,SqList L2,SqList *L3)
{
    ElemType *p1 = L1.elem;
    ElemType *p2 = L2.elem;

    while (p1<=&L1.elem[L1.length-1] && p2<=&L2.elem[L2.length-1])
    {
        if (*p1<*p2)
        {
            ListInsert(L3,L3->length,*p1);
            p1++;
        }else if (*p1>*p2)
        {
            ListInsert(L3,L3->length,*p2);
            p2++;
        }else
        {
            ListInsert(L3,L3->length,*p1);
            p1++;
            p2++;
        }   
    }
    
    if (p1>&L1.elem[L1.length-1])
    {
        while (p2<=&L2.elem[L2.length-1])
        {
            ListInsert(L3,L3->length,*p2);
            p2++;
        }
    }else
    {
        while (p1<=&L1.elem[L1.length-1])
        {
            ListInsert(L3,L3->length,*p1);
            p1++;
        }
    }
    return ;

}


void MergeList_2(SqList La,SqList Lb,SqList *Lc)
{  
#if 0
    ElemType* pa, * pb, * pc;
    ElemType* pa_last, * pb_last;
    
    pa = La.elem;                        // 指向La第一个元素
    pb = Lb.elem;                        // 指向Lb第一个元素
    
    // 没有使用InitList创建Lc
    (*Lc).listsize = (*Lc).length = La.length + Lb.length;
    pc = (*Lc).elem = (ElemType*) malloc((*Lc).listsize * sizeof(ElemType));
    if(pc == NULL) {
        exit(OVERFLOW);
    }
    
    pa_last = La.elem + La.length - 1;    // 指向La最后一个元素
    pb_last = Lb.elem + Lb.length - 1;    // 指向Lb最后一个元素
    
    // 如果La及Lb均未遍历完
    while(pa <= pa_last && pb <= pb_last) {
        if(*pa <= *pb) {
            *pc++ = *pa++;
        } else {
            *pc++ = *pb++;
        }
    }
    
    // 如果Lb已遍历完，但La还未遍历完，将La中剩余元素加入Lc
    while(pa <= pa_last) {
        *pc++ = *pa++;
    }
    
    // 如果La已遍历完，但Lb还未遍历完，将Lb中剩余元素加入Lc
    while(pb <= pb_last) {
        *pc++ = *pb++;
    }

#endif


    ElemType *pa,*pb,*pc;
    ElemType *pa_last,*pb_last;

    Lc->listsize = La.length + Lb.length;
    Lc->elem = (ElemType *)malloc(Lc->listsize*sizeof(ElemType));
    
    pa = La.elem;
    pb = Lb.elem;
    pc = Lc->elem;

    pa_last = La.elem + La.length -1;
    pb_last = Lb.elem + Lb.length -1;

    while (pa<=pa_last && pb<=pb_last)
    {
        if (*pa < *pb)
        {
            *pc++ = *pa++;
            ++Lc->length;
        }else if (*pa == *pb)
        {
            *pc++ = *pa++;
            pb++;
            ++Lc->length;
        }else
        {
            *pc++ = *pb++;
            ++Lc->length;
        }
    }
    
    while (pa <= pa_last)
    {
        *pc++ = *pa++;
        ++Lc->length;
    }
    while (pb <= pb_last)
    {
        *pc++ = *pb++;
        ++Lc->length;
    }
}